package offer;

import com.sun.xml.internal.fastinfoset.util.PrefixArray;

@FunctionalInterface
public interface PlatesBetweenCandles {
    int[] platesBetweenCandles(String s, int[][] queries);
}
class PlatesBetweenCandlesImpl1 implements PlatesBetweenCandles{

    @Override
    public int[] platesBetweenCandles(String s, int[][] queries) {
        int queryNum = queries.length;
        int[] ans = new int[queryNum];
        for (int i = 0; i < queryNum; i++) {
            ans[i] = query(s, queries[i]);
        }
        return ans;
    }
    private int query(String s, int[] query){
        int left = query[0], right = query[1];
        int count = 0;
        boolean existsLeftCandle = false, existsRightCandle = false;
        while(left < right){
            if(s.charAt(left) != '|'){
                left++;
            }else {
                break;
            }
        }
        while(left < right){
            if(s.charAt(right) != '|'){
                right--;
            }else {
                break;
            }
        }
        for(int i = left + 1; i < right; i++){
            if(s.charAt(i) == '*'){
                count++;
            }
        }
        return count;
    }
}
class PlatesBetweenCandlesImpl2 implements PlatesBetweenCandles{

    @Override
    public int[] platesBetweenCandles(String s, int[][] queries){
        int n = s.length();
        int[] left = new int[n];
        int[] right = new int[n];
        int[] ans = new int[queries.length];
        int[] preSum = new int[n];
        int l = -1, r = -1;
        for (int i = 0; i < n; i++) {
            if(s.charAt(i) == '|'){
                right[i] = i;
                l = i;
            }else{
                right[i] = l;
            }
        }
        for(int i = n - 1; i >= 0; i--){
            if(s.charAt(i) == '|'){
                left[i] = i;
                r = i;
            }else{
                left[i] = r;
            }
        }
        preSum[0] = s.charAt(0) == '|' ? 0 : 1;
        for (int i = 1; i < n; i++) {
            if(s.charAt(i) == '*'){
                preSum[i] = preSum[i - 1] + 1;
            }else {
                preSum[i] = preSum[i - 1];
            }
        }
        for (int i = 0; i < ans.length; i++) {
            int leftBound = left[queries[i][0]];
            int rightBound = right[queries[i][1]];
            if(leftBound == -1 || rightBound == -1 || leftBound >= rightBound){
                ans[i] = 0;
            }else{
                int count = 0;
                ans[i] = preSum[rightBound] - preSum[leftBound];
            }
        }
        return ans;
    }
}